package com.itheima.Array.sort;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

/**
 * @Author: Ethan Yankang
 * @Program: code-random-recordings
 * @Date: 2024-08-19 13:37
 **/
public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
            int mid = (left + right) / 2;
            // 递归地对两个子数组进行排序(实际上的排序动作在下面，单这一条语句仅仅分割)

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            // 排序并合并两个有序子数组
            merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 创建临时数组
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        // 拷贝数据到临时数组 arraycopy是复制以长度为依据的数组复制函数
        System.arraycopy(arr, left, leftArr, 0, n1);
        System.arraycopy(arr, mid + 1, rightArr, 0, n2);

        // 合并临时数组
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        // 拷贝剩余元素
        while (i < n1) {
            arr[k++] = leftArr[i++];
        }

        while (j < n2) {
            arr[k++] = rightArr[j++];
        }
    }
}

